在多道程序环境下，内存中存在着多个进程，其数目往往多余处理机数目，这就要求系统能够按照某种算法，动态地将处理机分配给处于就绪状态的一个进程，使之执行。

处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题。

3.1 处理机调度的层次和调度算法的目标

调度实质是一种资源分配，处理机调度是对处理机资源进行分配。

3.1.1 处理机调度的层次

  1. 高级调度

    高级调度又称长程调度或作业调度，调度对象是作业。

    主要功能：根据某种算法，决定将处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。

    主要用于多道批处理系统中，分时和实时系统中不设置高级调度。

  2. 低级调度

    低级调度又称为进程调度或短程调度，调度对象是进程（或内核级线程）。

    主要功能：根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分派给被选中的进程。

    进程调度是最基本的一种调度，多道批处理、分时和实时系统都必须配置这级调度。

  3. 中级调度

    中级调度又称内存调度。将暂时不能运行的进程调至外存等待，此时进程状态称为挂起态。

    引入目的：提高内存利用率和系统吞吐量

进程调度运行频率最高，因此称为短程调度。作业调度周期较长，因此称为长程调度。中级调度的运行频率介于两者之间，因此称为中级调度。

3.1.2 处理机调度算法的目标

处理机调度算法的共同目标：

  1. 资源利用率。为了提高资源利用率，应使系统中的处理机和其它资源都尽可能的保持忙碌状态。

    处理机利用率计算：$CPU的利用率 = \frac {CPU有效工作时间}{CPU有效工作时间 + CPU空闲时间}$

  2. 公平性。公平性是指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。公平性是相对的。

  3. 平衡性。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。

  4. 策略强制执行。对所制定的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

批处理系统的目标：

  1. 平均周转时间短。

    周转时间：作业被提交给系统开始，到作业完成为止的这段时间间隔，包括四部分：

    • 作业在外存后备队列上等待（作业）调度的时间
    • 进程在就绪队列上等待进程调度的时间
    • 进程在CPU上执行的时间
    • 进程等待I/O操作完成的时间

  2. 系统吞吐量高。

    吞吐量是指在单位时间内系统所完成的作业数，与批处理作业的平均长度有关

  3. 处理机利用率高

分时系统的目标：

  1. 响应时间快

    响应时间：从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔。

  2. 均衡性，指系统响应时间的快慢应与用户所请求服务的复杂性相适应。

实时系统的目标：

  1. 截止时间的保证
  2. 可预测性

3.2 作业与作业调度

在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。操作员把用户提交的作业通过相应的输入设备输入到磁盘存储器，并保存在一个后备队列中，再由作业调度程序将其从外存调入内存。

3.2.1 批处理系统中的作业

作业：作业是一个比程序更广泛的概念，不仅包含了通常的程序和数据，还应配有一份作业说明书

作业步：通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，每个加工步骤称为一个作业步，各作业步之间存在着相互联系。

为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，保存了系统对作业进行管理和调度所需要的全部信息。

作业运行的三个阶段和三种状态：

  • 收容阶段，作业进入后备队列，后备状态
  • 运行阶段，作业进入就绪队列开始到运行结束前，运行状态
  • 完成阶段，作业运行完成或提前结束，完成状态

3.2.2 作业调度的主要任务

作业调度的主要任务是，根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源，将新创建的进程排在就绪队列上等待调度。因此作业调度又称为接纳调度。

每次执行作业调度时，都需要作出以下两个决定：

  • 接纳多少个作业

    取决于多道程序度，即允许多少个作业同时在内存中运行

  • 接纳哪些作业

    取决于所采用的调度算法

3.2.3 先来先服务（FCFS）和短作业优先（SJF）调度算法

  1. 先来先服务（FCFS）调度算法

    最简单的调度算法，既可用作业调度，也可用于进程调度。

  2. 短作业优先（SJF）调度算法

    以作业长短计算优先级，作业越短优先级越高，可以分别作用域作业调度和进程调度。

    缺点：

    • 必须预知作业的运行时间
    • 对长作业非常不利，长作业的周转时间明显增长
    • 在采用FCFS算法时，人-机无法交互
    • 未完全考虑作业的紧迫程度

3.3.3 优先级调度算法和高响应比优先调度算法

  1. 优先级调度算法（PSA）

    FCFS：作业的等待时间就是作业的优先级

    SJF：作业的长短就是作业的优先级

    优先级调度算法是基于作业的紧迫程度，由外部赋予作业优先级，调度算法更加该优先级进行调度。

    可用于作业调度，也可用于进程调度。

  2. 高响应比优先调度算法（HRRN）

    FCFS：只考虑了作业的等待时间，忽略了作业的运行时间

    SJF：只考虑了作业的运行时间，忽略了作业的等待时间

    高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业运行时间的调度算法。

    HRRN为每个作业引入一个动态优先级，随等待时间延长而增加：$优先权= \frac {等待时间+要求服务时间}{要求服务时间}$

    等待时间与服务时间之和就是响应时间，故优先级相当于响应比$R_p$：$R_p = \frac {等待时间+要求服务时间}{要求服务时间} = \frac {响应时间}{要求服务时间}$

3.3 进程调度

进程在操作系统内核程序临界区中不能进行调度与切换。 √ 进程处于临界区时不能进行处理机调度。 ×

3.3.1 进程调度的任务、机制和方式

进程调度的任务有三：

  1. 保存处理机现场信息
  2. 按照某种算法选取进程
  3. 把处理器分配给进程

为了实习进程调度，在进程调度机制中，应具有三个基本部分：

  1. 排队器
  2. 分派器
  3. 上下文切换器

image-20200629103037266

进程调度方式：

  1. 非抢占方式

    处理机一旦分配给进程后，直至进程完成或被阻塞，才能把处理机分配给其它进程。

    采用非抢占式调度方式时，可能引起进程调度的因素：

    • 正在执行的进程运行完毕，或因发生某事情而无法再继续运行
    • 正在执行中的进程因提出I/O请求而暂停执行
    • 在进程通信或同步过程中，执行了某种原语操作

    非抢占式的优点：实现简单，系统开销小，适用于大多数的批处理系统，但不适用于分时系统和大多数实时系统。

  2. 抢占方式

    允许调度程序根据某种原则， 去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。

    ”抢占“不是一种任意性行为，必须遵循一定的原子：

    • 优先级原则，优先级高的可以抢占优先级低的
    • 短进程优先原则
    • 时间片原则，进程的时间片用完则重新调度

3.3.2 轮转调度算法

在分时系统中，最简单也是较常用的是基于时间片的轮转（RR）调度算法。该算法采用了非常公平的处理机分配方式，即让就绪队列上的每个进程每次仅运行一个时间片。

在轮转（RR）中，系统将所有就绪进程按FCFS策略排成一个就绪队列。系统每隔一段时间便产生一次中断，激活进程调度程序进行调度，把CPU分配给队首进程，令其执行一个时间片。

在RR调度算法中，进程切换的时机分为2种情况：

  1. 时间片未用完，而进程已经完成
  2. 时间片用完，进程尚未执行完毕

在轮转算法中，时间片的大小对系统性能影响很大。若时间片太小，就会频繁地执行进程调度和进程上下文切换，增加系统开销；若时间片过长，则RR算法便退化成FCFS算法，无法满足短作业和交互式用户的需求。

一个较为可取的时间片大小是略大于一次典型的交互所需要的时间，使大多数交互式进程能在一个时间片内完成，从而获得很小的响应时间。

3.3.3 优先级调度算法

进程调度时，把处理机分配给就绪队列中优先级最高的进程。

该算法可分为两类：

  • 非抢占式优先级调度算法

  • 抢占式优先级调度算法

    进程执行期间出现了另外一个优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程

优先级的类型：

  • 静态优先级

    进程创建时确定，在进程的整个运行期间保持不变。

    确定进程优先级大小的依据有三个：

    • 进程类型。系统进程高于用户进程
    • 进程对资源的需求。资源需求少的进程优先级高
    • 用户要求

    静态优先级简单易行，系统开销小，但不够精确，可能会出现优先级低的进程长期没有被调用的情况。

  • 动态优先级

    进程创建的时候，先赋予一个优先级，其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。

3.3.4 多队列调度算法

该算法将系统中的进程就绪队列从一个拆分为若干个，根据不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同就绪队列本身也可以设置不同的优先级。

3.3.5 多级反馈队列调度算法

调度机制描述如下：

  1. 设置多个就绪队列，为每个就绪队列赋予不同的优先级，为不同队列中的进程所赋予的执行时间片的大小也各不相同。

    image-20200629144608500

  2. 每个队列都采用FCFS算法，队列中的进程采用RR调度算法

  3. 按队列优先级调度，优先级高的队列中的进程先运行，只有高优先级队列为空时，才运行低优先级队列中的进程，过程是可抢占的

3.3.6 基于公平原则的调度算法

  1. 保证调度算法

    向用户作出的保证不是优先运行，而是明确的性能保证。一种比较容易实现的性能保证是处理机分配的公平性，如果系统中有n个相同类型的进程同时运行，为公平起见，必须保证每个进程都获得相同的处理机时间$1 \over n$。

  2. 公平分享调度算法

    分配给每个进程相同的处理机时间，对进程是公平的，但如果每个用户的进程数不同，就会发生对用户的不公平问题。

    该调度算法中，公平性是针对用户而言的，使所有用户能获得相同的处理机时间，或所要求的时间比较。

3.4 实时调度

在实时系统中，可能存在两类不同性质的实时任务，即HRT任务和SRT任务，它们都联系着一个截止时间。

3.4.1 实现实时调度的基本条件

  1. 提供必要的信息

    1. 就绪时间，某任务成为就绪状态的起始时间
    2. 开始截止时间和完成截止时间，典型的实时应用只须知其一
    3. 处理时间
    4. 资源要求
    5. 优先级
      1. “绝对”优先级：某任务的开始截止时间错误势必引起故障
      2. “相对“优先级：某任务的开始截止时间错误对任务的继续运行无重大影响

  2. 系统处理能力强

  3. 采用抢占式调度机制

  4. 具有快速切换机制

    该机制应具有以下两方面的能力：

    • 对中断的快速响应能力
    • 快速的任务分派能力

3.4.2 实时调度算法的分类

根据实时任务的性质，可将实时调度的算法分为硬实时调度算法和软实时调度算法

按调度方式，可分为非抢占调度算法和抢占调度算法

  1. 非抢占式调度算法
    1. 非抢占式轮转调度算法
    2. 非抢占式优先调度算法
  2. 抢占式调度算法
    1. 基于时钟中断的抢占式优先级调度算法
    2. 立即抢占的优先级调度算法

image-20200629155908668

3.4.3 最早截止时间优先EDF算法

根据任务的截止时间确定任务的优先级，任务的截止时间越早，其优先级越高，具有最高截止时间的任务排在队列的队首，作为第一个调度的任务。

  1. 非抢占式调度方式用于非周期实时任务

    image-20200629160235357

  2. 抢占式调度方式用于周期性实时任务

    image-20200629160305158

3.4.4 最低松弛度优先LLF算法

该算法在确定任务的优先级时，根据的是任务的紧急（或松弛）程度。任务越紧急，优先级越高。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在最前面，调度程序选择队列中的首任务只须。

松弛度 = 必须完成时间 - 其本身的运行时间 - 当前时间

该算法主要用于可抢占调度方式。

3.4.5 优先级倒置

当前OS广泛采用优先级调度和抢占方式，然而系统中存在着影响进程运行的资源而可能产生”优先级倒置“的现象，即高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞。

假设有三个完全独立的进程 P1、P2、P3，优先级大小P1>P2>p3
P1和P3通过共享的一个临界资源进行交互

P1:	...P(mutex);	CS-1;	V(mutex);
P2:	...program2...;
P3:	...P(mutex);	CS-3;	V(mutex);

假如P3最先执行，执行P操作后进入临界区，接着P2就绪，抢占了处理机，再接着P1就绪，抢占了处理机，而当P1执行P操作时，因为临界资源被P3占用，故P1被阻塞，P2继续运行，P2运行完后P3接着运行，直到P3执行V操作后才轮到P1执行。

根据优先级原则，高优先级进程应当能优先执行，但在此例中，P1和P3共享”临界资源“，而出现了不合常理的现象，高优先级进程P1因P3进程被阻塞，又因为P2进程的存在延长了P1被阻塞的时间，而且被延长的时间是不可预知和无法限定的。由此产生的”优先级倒置“是非常有害的，不应该出现在实时系统中。

优先级倒置的解决方法：

  1. 最简单的解决方法是规定：假如进程P3在进入临界区后P3所占的处理机就不允许被抢占。这种方法在临界区比较短的情况是可行的，反之效果就不是很令人满意

  2. 比较实用的方法是建立在动态优先级继承基础上的。该方法规定：当高优先级进程P1要进入临界区，去使用临界资源R，如果已有一个低优先级进程P3正在使用该资源，此时一方面P1被阻塞，另一方面由P3继承P1的优先级，并一直保持到P3退出临界区。

    这样的目的是：不让比P3优先级高，但比P1优先级低的进程如P2插进来，导致延缓P3退出临界区

3.5 死锁问题

3.5.1 资源问题

系统中有许多不同类型的资源，其中可以引起死锁的主要是，需要互斥访问方法的、不可以被抢占的资源，即临界资源，如打印机、数据文件、队列、信号量等。

可重用性资源是一种可供用户重复使用多次的资源，具有的性质是：

  • 每个可重用性资源中的单元只能分配给一个进程使用，不允许多个进程共享
  • 进程在使用可重用资源时，须按顺序：
    • 请求资源
    • 使用资源
    • 释放资源
  • 系统中每一类可重用性资源中的单元数目是相对固定 ，进程在运行期间既不能创建也不能删除它

可消耗性资源又称为临时性资源，它是在进程运行期间，由进程动态地创建和消耗的，具有如下性质：

  • 每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的
  • 进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区，以增加该资源类的单元数目
  • 进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中

可把系统中的资源分成两类，

  • 一类是可抢占性资源，是指某进程活动这类资源后，该资源可以再被其它进程或系统抢占
    • 优先级高的可以抢占优先级低的进程的处理机
    • 内存资源紧张时，还可抢占进程的内存空间
  • 另一类资源是不可抢占性资源，即一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程中用完后自行释放
    • 进程在刻录光盘时，抢占必然会损坏光盘
    • 磁带机、打印机等也属于不可抢占性资源

3.5.2 计算机系统中的死锁

死锁的起因，通常是源于多个进程对资源的争夺，不仅对不可抢占性资源进行争夺时会引起死锁，而且对可消耗性资源进行争夺时，也会引起死锁。

  1. 竞争不可抢占性资源引起死锁

    P1: ...		P(f1);	P(f2);	...
P2:	...		P(f2);	P(f1);	...

    两个进程P1和P2并发执行时，如果P1先打开f1，同时P2打开f2，此时P1试图打开f2而P2试图打开f1，因此这两个进程都将会无限期待地等待下去，形成死锁。

  2. 竞争可消耗性资源引起死锁

    P1:	...send(p2,m1);	receive(p3,m3);	...
P2:	...send(p3,m2);	receive(p1,m1);	...
P3:	...send(p1,m3);	receive(p2,m2);	...

    三个进程都先发送信息，再接受信息，则可以顺利执行。

    三个进程都先接受信息，再发送信息，则三个进程会永远阻塞在它们的receive操作。

  3. 进程推进顺序不当引起死锁

3.5.3 死锁的定义、必要条件和处理方法

如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的（Deadlock）。

虽然进程在运行过程中可能会发生死锁，但产生死锁是必须具备一定条件的，四个必要条件若有一个不成立，死锁就不会发生：

  1. 互斥条件。进程对资源互斥使用
  2. 请求和保持条件。进程以获得一个资源，又提出新的资源请求。
  3. 不可抢占条件。进程获得的资源是不可抢占的
  4. 循环等待条件。发生死锁时，必然存在一个“进程-资源”的循环等待链。

处理死锁的方法可归结为四种：

  1. 预防死锁。通过设置限制条件
  2. 避免死锁。资源分配时防止系统进入不安全状态
  3. 检查死锁
  4. 解除死锁。当检查出死锁后，采取一些措施解除死锁，常用的方式是撤销一些进程，回收它们的资源

3.6 预防死锁

预防死锁的方法是通过破坏产生死锁的四个必要条件的一个或几个，由于互斥条件是非共享设备必须的，不仅不能改变，还必须保证，因此主要是破坏后三个条件。

3.6.1 破坏“请求和保持“条件

系统必须保证：当一个进程在请求资源时，它不能持有不可抢占资源。可以通过两个不同的协议实现：

  1. 第一种协议

    进程在开始运行之前，必须一次性地申请其运行过程所需要的全部资源。

    优点：简单、易行且安全

    缺点：资源严重浪费、进程经常会发生饥饿现象

  2. 第二种协议

    允许进程只获得运行初期所需要的资源便开始运行，运行过程逐步释放自己已用毕的资源，然后再请求新的所需资源。

    优点：使进程更快地完成任务，提高了设备的利用率，减少进程发生饥饿的机率。

3.6.2 破坏”不可抢占“条件

当一个已经保持了某些不可抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经满足的所有资源，待以后需要时再重新申请。

意味着进程已占有资源会被暂时释放。

该方法实现起来比较复杂，付出的代价较大，可能造成进程前一阶段工作失效，反复申请和释放资源增加了系统开销，可能使进程被无限推迟，延长了进程的周转周期，降低了系统吞吐量。

3.6.3 破坏”循环等待“条件

对系统中所有资源类型进行线性排序，并赋予不同序号，然后规定：每个进程必须按序号递增的顺序请求资源。

规定每种资源的序号是十分重要的，通常应根据大多数进程需要资源的先后顺序来确定。

优点：相对前两种策略，资源利用率高，系统吞吐量高。

存在问题：

  • 序号必须相对稳定，限制了新类型资源的增加
  • 进程资源获取顺序与序号不完全相同，造成资源的浪费
  • 限制了用户进行简单自主地编程

3.7 避免死锁

3.7.1 系统安全状态

把系统的状态分为安全状态和不安全状态。当系统处于安全状态时可以避免发生死锁，反之，则可能进入死锁状态。

安全状态：系统按照某种进程推进顺序（P1,P2,...,Pn)为每个进程Pn分配其所需要资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称（P1,P2,...,Pn)为安全序列。

如果系统无法找到一个安全序列，则称系统处于不安全状态，有可能进入死锁状态。反之，只要系统处于安全状态，系统便可避免进入死锁状态。

3.7.2 利用银行家算法避免死锁

3.8 死锁的检查与解除

3.8.1 死锁的检测

为了能对系统中是否已发送了死锁进行检查，在系统中必须：

  1. 保存有关资源的请求和分配信息
  2. 提供一种算法，利用这些信息检查系统是否已进入死锁状态

系统死锁，可利用资源分配图来描述。

系统处于S状态时，S为死锁的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。

资源分配图经一系列简化后，若能消去图中所有的边，则所有进程节点成为孤立结点，称该图是可完全简化的；反之则该图是不可完全简化的。

image-20200630171708226

3.8.2 死锁的解除

检测出死锁后应该采取相应措施以解除死锁，最简单的处理措施就是通知操作员，人工处理死锁；另一种措施是利用死锁解除算法，把系统从死锁状态中解脱出来。

常采用的解除死锁方法：

  • 抢占资源。从一个或多个进程中抢占足够多的资源分配给死锁进程，以解除死锁状态
  • 终止（或撤销）进程。打破死锁循环环路。

终止进程的方法：

  1. 终止所有死锁进程：付出代价过大

  2. 逐个终止进程

    按照某种顺序，逐个终止进程，直至有足够的资源，以打破循环等待。

    选择终止进程时的考虑因素：

    1. 进程优先级大小
    2. 进程已执行时间，还需要多少时间
    3. 进程在运行中已使用多少资源，还需多少资源
    4. 进程的性质是交互式的还是批处理式的

image-20200630172856995

将每次终止进程的代价作为权值，状态作为节点，生成一颗树，寻找根节点倒叶子节点的最短路径。